Non-Clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup Times

摘要

Consider a problem in which $n$ jobs that are classified into $k$ typesarrive over time at their release times and are to be scheduled on a singlemachine so as to minimize the maximum flow time. The machine requires a setuptaking $s$ time units whenever it switches from processing jobs of one type tojobs of a different type. We consider the problem as an online problem whereeach job is only known to the scheduler as soon as it arrives and where theprocessing time of a job only becomes known upon its completion(non-clairvoyance). We are interested in the potential of simple "greedy-like" algorithms. Weanalyze a modification of the FIFO strategy and show its competitiveness to be$\Theta(\sqrt{n})$, which is optimal for the considered class of algorithms.For $k=2$ types it achieves a constant competitiveness. Our main insight isobtained by an analysis of the smoothed competitiveness. If processing times$p_j$ are independently perturbed to $\hat p_j = (1+X_j)p_j$, we obtain acompetitiveness of $O(\sigma^{-2} \log^2 n)$ when $X_j$ is drawn from a uniformor a (truncated) normal distribution with standard deviation $\sigma$. Theresult proves that bad instances are fragile and "practically" one might expecta much better performance than given by the $\Omega(\sqrt{n})$-bound.